package com.kobe.game_20;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

/**
 * 
 * By starting at the top of the triangle below and moving to adjacent numbers
 * on the row below, the maximum total from top to bottom is 23.
 * 
 * That is, 3 + 7 + 4 + 9 = 23.
 * 
 * Find the maximum total from top to bottom of the triangle below:
 * 
 * 
 * NOTE: As there are only 16384 routes, it is possible to solve this problem by
 * trying every route. However, Problem 67, is the same challenge with a
 * triangle containing one-hundred rows; it cannot be solved by brute force, and
 * requires a clever method! ;o)
 * 
 * 
 * 
 */
public class Game18 {

    private static int[][] getTriangleArray() throws IOException {
        FileReader reader = new FileReader(new File(
                "src/source/Game18_Triangle.txt"));
        BufferedReader bufferedReader = new BufferedReader(reader);

        int[][] triangleArray = new int[15][15];
        String tempLine = null;
        while ((tempLine = bufferedReader.readLine()) != null) {
            String[] tempInt = tempLine.split(" ");
            for (int i = 0; i < tempInt.length; i++) {
                triangleArray[tempInt.length - 1][i] = Integer
                        .parseInt(tempInt[i]);
            }
        }
        return triangleArray;
    }

    public static void main(String[] args) throws IOException {
        int[][] triangleArray = getTriangleArray();
        for (int i = 1; i < triangleArray.length; i++) {
            for (int m = 0; m < triangleArray[i].length; m++) {
                int temp = triangleArray[i][m];
                if (m == 0) {
                    triangleArray[i][m] = triangleArray[i - 1][m] + temp;
                } else {
                    triangleArray[i][m] = Math.max(triangleArray[i - 1][m - 1],
                            triangleArray[i - 1][m])
                            + temp;
                }
            }
        }
        int result = 0;

        for (int i = 0; i < triangleArray[14].length; i++) {
            if (triangleArray[14][i] > result) {
                result = triangleArray[14][i];
            }
        }

        System.out.println("result is :  " + result);
    }
}
